Electronic or digital signatures are used to authenticate information, that is to securely tie the contents of an electronic document to a signer, more precisely, to the signer's public key. Only the true signer should be able to produce valid signatures, and anyone should be able to verify them in order to convince oneself that the signer indeed signed the document. While many digital signature schemes have been proposed so far, a few are used in practice today.
Ordinary digital signature schemes suffer from a fundamental shortcoming: once the secret key is leaked, for example because a hacker managed to break into the signer's computer, and, when this leakage is detected, the public key is revoked then all signatures produced by the signer become reputable, i.e., it is no longer possible to distinguish whether a signature was produced by the signer or the hacker. Therefore ordinary signature schemes can pre se not provide non-repudiation. One possibility to achieve non-repudiation is to use a so-called time-stamping service. Here each signature is sent to a trusted third party who signs a message containing the signature and the current date and time. A signature is considered non-reputable if it was time-stamped before the signer revoked her public key. Hence, assuming that the trusted third party's key is never leaked, non-repudiation is guaranteed. However, this solution requires frequent interaction with a trusted third party, e.g., the time-stamping service, which is not desirable.
Another possibility is to change the keys frequently, i.e., to use a different key pair each day and delete all the secret keys of past days. It then is understood that if a day has passed without that the user has revoked that day's key then all the signatures made with respect to the key are non-reputable. This either requires again frequent interaction with the trusted third party, or, the public key becomes large, i.e., a list of many public keys. Forward secure signature schemes as introduced by R. Anderson in “Two remarks on public-key cryptography”, Manuscript, presented by the author at the 4th ACM CCS (1997), September 2000, and formalized by Bellare and Miner in “A forward-secure digital signature scheme”, In Michael Wiener, editor, Advances in Cryptology—CRYPTO '99, volume 1666 of LNCS, pages 431-448, Springer Verlag, 1999, solve this problem by having only one public key but many secret keys—one for each time period. In fact, most forward secure signature schemes allow one to derive the secret key of the current time period from the one of the previous period in a one-way fashion.
In principle, a forward secure signature scheme can be obtained from any ordinary signature scheme: the signer chooses new secret and public keys for each time period. The public key of the forward secure signature scheme become the set of the ordinary public keys index by the time period for which they are valid. To sign a message the signer uses the secret key of that period. Once a time period has passed, the signer deletes the respective secret key. It is easy to see that this scheme is forward secure. However, the scheme is rather inefficient in terms of (public and secret) storage.
However, current forward secure signature schemes suffer from the following problem. In case of a hacker's break-in all the signatures made in this time-period have to be recalled and the (honest) signer needs to re-issue them. One solution to this is to use small time-periods which only works if the complexity of the key update is comparable to the complexity of signing.
From the above it follows that there is a call for an improved forward secure signature scheme that is more secure and efficient. The scheme should furthermore allow to react on a hacker's break-in immediately without re-issuing signatures for the past.